package com.company.笔试.克隆图;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {
    private Map<Node, Node> map = new HashMap<>();
    public Node cloneGraph(Node node) {
        if(node == null) return node;
        if(map.get(node)!=null) {
            return map.get(node);
        }

        Node copy = new Node(node.val,new ArrayList<Node>());
        map.put(node,copy);
        for(Node neighbor:node.neighbors){
            
            Node cloneNeighbor = cloneGraph(neighbor);
            copy.neighbors.add(cloneNeighbor);
        }
        return copy;
    }
}

class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}